package entidades;

public class Heap {

	Vetor vetor;
	int tamanhoHeap;
	int indiceDoMaior = 1;

	private void consultaIndiceDoMaior() {
		for (int i = 1; i < vetor.getTamanho() - 1; i++) {
			if (vetor.getValor(i) > vetor.getValor(indiceDoMaior)) {
				indiceDoMaior = i;
			}
		}
	}

	public Heap(Vetor vetor) {
		super();
		this.vetor = vetor;
		consultaIndiceDoMaior();
	}

	private int pai(int indice) {
		return indice/2;
	}

	private int filhosEsquerda (int indice) {
		return (2 * indice) - 1;
	}

	private int filhosDireita (int indice) {
		return (2 * indice); 
	}

	private void Heapify (int indice) {

		int esq = filhosEsquerda(indice);
		int dir = filhosDireita(indice);

		if ((esq <= tamanhoHeap - 1) && (dir <= tamanhoHeap - 1)) {

			if (vetor.getValor(esq) > vetor.getValor(dir)) {
				indiceDoMaior = esq;
				if (vetor.getValor(esq) > vetor.getValor(indice)) {
					indiceDoMaior = esq;
				}				
			}
			else {
				indiceDoMaior = indice;
				if (vetor.getValor(dir) > vetor.getValor(indice)) {
					indiceDoMaior = dir;
				}				
			}

			if (indiceDoMaior != indice) {
				trocar(indice - 1, indiceDoMaior);
				Heapify(indiceDoMaior);
			}
		}
		
		else {
			
			if (esq <= tamanhoHeap - 1) {

				indiceDoMaior = indice;
				if (vetor.getValor(esq) > vetor.getValor(indice)) {
					indiceDoMaior = esq;
				}				
			}

			if (indiceDoMaior != indice) {
				trocar(indice - 1, indiceDoMaior);
				Heapify(indiceDoMaior);
			}
		}
	}

	private void trocar(int indice1, int indice2) {

		int aux = vetor.getValor(indice1);

		vetor.setValor(indice1, vetor.getValor(indice2));
		vetor.setValor(indice2, aux);
	}

	public void construir() {
		tamanhoHeap = vetor.getTamanho();
		for (int i = (tamanhoHeap / 2); i >= 1; i--) {
			Heapify(i);
		}
	}

	public String imprimir() {
		return this.vetor.imprimir();
	}
}